package org.example.myleet.p768;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int maxChunksToSorted(int[] arr) {
        int[] sorted = new int[arr.length];
        System.arraycopy(arr, 0, sorted, 0, arr.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> numMapCount = new HashMap<>();
        int chunkCount = 0;
        for (int i = 0; i < arr.length; ++i) {
            //遇到arr的数字则+1计数
            Integer count = numMapCount.getOrDefault(arr[i], 0);
            ++count;
            if (0 == count) {
                numMapCount.remove(arr[i]);
            } else {
                numMapCount.put(arr[i], count);
            }
            //遇到sorted的数字则-1计数
            count = numMapCount.getOrDefault(sorted[i], 0);
            --count;
            if (0 == count) {
                numMapCount.remove(sorted[i]);
            } else {
                numMapCount.put(sorted[i], count);
            }
            //如果没有数字被跟踪，则成功找到一个分块
            if (0 == numMapCount.size()) {
                ++chunkCount;
            }
        }
        return chunkCount;
    }
}
